No description has been provided for this image DDS 0970252 - Autonomous Planning Under Uncertainty


Moshe Rafaeli - moshiktech@gmail.com
Tamir Shazman - tmyr@campus.technion.ac.il

Course website: https://anpl-technion.github.io/Teaching/#POMDP
Course forum and announcements: https://piazza.com/technion.ac.il/fall2025/0970252

external-probability-data-science-becris-lineal-color-becris Tutorial 1: Foundations of Probability, Bayesian Inference, Environment Representation and Julia¶


Notebook kernel: Julia (recommended version ≥ 1.11)

Packages used (install if needed):

In [1]:
using Pkg
Pkg.add(["Distributions", "LinearAlgebra", "Random", "Statistics", "Plots", "StatsBase", "Combinatorics", "POMDPTools"])
   Resolving package versions...
  No Changes to `C:\Users\moshi\.julia\environments\v1.11\Project.toml`
  No Changes to `C:\Users\moshi\.julia\environments\v1.11\Manifest.toml`
In [2]:
using LinearAlgebra, Random, Distributions, Statistics, Plots, StatsBase, Combinatorics, POMDPTools

Basic probability - discrete random variables¶


In [3]:
Random.seed!(0970252) # we will use this seed for all random processes in the tutorials

# PMF for biased coin (Heads with prob 0.7)
p_head = 0.7
support = ["H","T"]
pmf = Dict("H"=>p_head, "T"=>1-p_head)

# sample many times and estimate empirical PMF
n = 10000
samples = rand(Binomial(1,p_head), n)   # 1 ~ H, 0 ~ T
emp_counts = countmap(samples)
emp_pmf = Dict("H" => emp_counts[1]/n, "T" => emp_counts[0]/n)

# show the true PMF vs the empirical PMF
println("True PMF:\t", pmf)
println("Empirical PMF:\t", emp_pmf)
True PMF:	Dict("T" => 0.30000000000000004, "H" => 0.7)
Empirical PMF:	Dict("T" => 0.2966, "H" => 0.7034)

Continuous random variables - PDF, sampling, histogram¶


In [4]:
Random.seed!(0970252)

# PDF for Normal distribution
μ, σ = 2.0, 3.0
xs = range(μ-4σ, μ+4σ, length=200)
x_pdf = exp.(-(xs .- μ).^2 ./ (2*(σ^2))) ./ sqrt(2π*(σ^2))

# samples from Normal distribution
rv = Normal(μ, σ)
x_empirical = rand(rv, 10000)

# plot histogram of samples and overlay true PDF
histogram(x_empirical, bins=50, normalize=true, label="empirical")
plot!(xs, x_pdf, label="pdf (Normal)")
Out[4]:

Joint and conditional distributions, marginalization¶


Example: Two Random Variables $X,Y$, with the following joint distribution, and individual distribution:

$P(X=x,Y=y)$ $y=0$ $y=1$
$x=0$ $0.1$ $0.2$ $\rightarrow P(X=0)=0.3$
$x=1$ $0.3$ $0.4$ $\rightarrow P(X=1)=0.7$
$\downarrow \\ P(Y=0)=0.4$ $\downarrow \\ P(Y=1)=0.6$
In [5]:
# Example discrete joint distribution for (X,Y)
pXY = Dict( (0,0)=>0.1,
            (0,1)=>0.2,
            (1,0)=>0.3,
            (1,1)=>0.4)

# marginalize to get p(X)
pX = Dict(0 => pXY[(0,0)]+pXY[(0,1)],
          1 => pXY[(1,0)]+pXY[(1,1)])
# conditional p(X|Y=1)
pY1 = pXY[(0,1)] + pXY[(1,1)]
pX_given_Y1 = Dict(x => pXY[(x,1)]/pY1 for x in (0,1))

println("P(X) =\t\t", pX)
println("P(X|Y=1) =\t", pX_given_Y1)
P(X) =		Dict(0 => 0.30000000000000004, 1 => 0.7)
P(X|Y=1) =	Dict(0 => 0.3333333333333333, 1 => 0.6666666666666666)

Chain rule and Bayes' rule¶


Example: We have a machine that detects wether a patient is sick.

The patient can either be sick or be healthy, i.e. $X = \{\mathrm{healthy, sick}\}$. The probability of a patient to be sick is 1%.
The machine returns $\mathrm{Positive}$ if it detects the patient is sick or $\mathrm{Negative}$ otherwise, i.e. $Y = \{\mathrm{Positive, Negative}\}$.
The machine returns $\mathrm{Positive}$ 95% of the times when the patient is actually sick, and returns $\mathrm{Positive}$ 3% of the times when the patient is actually healthy.

What is the probability a patient is sick, given the machine returned $\mathrm{Positive}$?

Bayes Rule: $$ \mathbb{P}(\mathrm{sick} \mid \mathrm{Positive}) = \frac{\mathbb{P}(\mathrm{Positive} \mid \mathrm{sick}) \cdot \mathbb{P}(\mathrm{sick})}{\mathbb{P}(\mathrm{Positive})} $$

Marginalization & Chain Rule: $$ \mathbb{P}(\mathrm{Positive}) = \mathbb{P}(\mathrm{Positive, sick}) + \mathbb{P}(\mathrm{Positive, healthy}) = \mathbb{P}(\mathrm{Positive \mid sick}) \cdot \mathbb{P}(\mathrm{sick}) + \mathbb{P}(\mathrm{Positive \mid healthy}) \cdot (1 - \mathbb{P}(\mathrm{sick})) $$

In [6]:
# probabilities for the medical test example
p_sick = 0.01
p_pos_given_sick = 0.95
p_pos_given_healthy = 0.03

# Bayes and Chain rules
p_pos = p_pos_given_sick*p_sick + p_pos_given_healthy*(1-p_sick)
p_sick_given_pos = (p_pos_given_sick * p_sick)/p_pos

println("P ( Sick | Positive ) = ", p_sick_given_pos)
P ( Sick | Positive ) = 0.2423469387755102

Expectation and covariance¶


In [7]:
Random.seed!(0970252)

μ, σ = 1.0, 2.0
# generate samples from Normal distribution
x = rand(Normal(μ, σ), 10000)
E_x = mean(x)
Var_x = var(x)

# generate samples from 2D Gaussian and estimate covariance matrix
μ1, σ1 = 0.0, 1.0
μ2, σ2 = 2.0, 1.5
X = [rand(Normal(μ1, σ1),5000) rand(Normal(μ2, σ2),5000)]
cov_est = cov(X)

println("1D Gaussian: mean = $(μ), variance = $(σ^2)")
println("Empirical mean = $(E_x), Empirical variance = $(Var_x)")
println()
println("2D Gaussian: true means = [$(μ1), $(μ2)], true variances = [$(σ1^2), $(σ2^2)]")
println("Empirical Covariance matrix:\n", repr("text/plain",cov_est))
1D Gaussian: mean = 1.0, variance = 4.0
Empirical mean = 0.9663147301780304, Empirical variance = 3.977300658987374

2D Gaussian: true means = [0.0, 2.0], true variances = [1.0, 2.25]
Empirical Covariance matrix:
2×2 Matrix{Float64}:
  1.01026    -0.0392326
 -0.0392326   2.29468

Gaussian distributions and information form¶


In [8]:
# Covariance form
μ = [1.0, -0.5]
Σ = [0.5 0.1; 0.1 0.2]

println("Covariance Form:")
println("μ = ", μ)
println("Σ = \n", repr("text/plain",Σ))
Covariance Form:
μ = [1.0, -0.5]
Σ = 
2×2 Matrix{Float64}:
 0.5  0.1
 0.1  0.2
In [9]:
# Information form
Λ = inv(Σ)
η = Λ * μ

println("Information Form:")
println("η = ", η)
println("Λ = \n", repr("text/plain",Λ))
Information Form:
η = [2.7777777777777777, -3.888888888888889]
Λ = 
2×2 Matrix{Float64}:
  2.22222  -1.11111
 -1.11111   5.55556
In [10]:
# back to covariance form
Σ2 = inv(Λ)
μ2 = Σ2 * η

println("Back to Covariance Form:")
println("Recovered μ = ", μ2)
println("Original μ = ", μ)
Back to Covariance Form:
Recovered μ = [0.9999999999999998, -0.5]
Original μ = [1.0, -0.5]
In [11]:
# PDF for distribution for Covariance form
xs = range(μ[1]-4*Σ[1,1], μ[1]+4*Σ[1,1], length=20)
ys = range(μ[2]-4*Σ[2,2], μ[2]+4*Σ[2,2], length=20)
x_cov_pdf = [exp(-0.5*([x,y]-μ)'*inv(Σ)*([x,y]-μ)) / (2π*sqrt(det(Σ))) for x in xs, y in ys]
x_inf_pdf = [exp(-0.5*([x,y]'*Λ*[x,y] - 2*η'*[x,y] + μ'*Λ*μ)) / (2π*sqrt(det(Σ))) for x in xs, y in ys]

# plot the two PDFs side by side
p1 = plot(xs, ys, x_cov_pdf, linetype=:surface, color=:matter, title="Covariance Form", legend=false)
p2 = plot(xs, ys, x_inf_pdf, linetype=:surface, color=:matter, title="Information Form", legend=false)
plot(p1, p2, layout=(1, 2), size=(800, 400))
Out[11]:

Bayesian Inference - The Tiger Problem¶


The Tiger Problem is a classic example in decision-making under uncertainty. We present now a simplified version of the problem (without rewards or actions).

Tiger POMDP

An agent faces two closed doors: behind one is a tiger, behind the other is treasure. The agent listens to the doors to gather information about the tiger's location.

  • States ($X$):

    • $X = \{\text{tiger-left},\ \text{tiger-right}\}$
  • Observations ($Z$):

    • $Z = \{\text{hear-left},\ \text{hear-right}\}$

The agent listens to the doors and receives an observation $z \in Z$ indicating which door the tiger might be behind, but the observation is noisy.

In [12]:
# The Tiger Problem Example
xs = [:TigerLeft, :TigerRight]  # state space
zs = [:HearLeft, :HearRight]    # observation space

# NOTE: you can change these parameters to see how the inference changes.
pX = Dict(x=>1/length(xs) for x in xs)   # prior P(X) - uniform
pZ_given_X = Dict(  :TigerLeft => Dict(:HearLeft=>0.8, :HearRight=>0.2),
                    :TigerRight => Dict(:HearLeft=>0.3, :HearRight=>0.7) ) # likelihood P(Z|X) - observation model

"""
Perform Bayesian Inference to compute the posterior distribution _P(X|z)_ given:
- `xs`: support of _X_ (discrete and finite)
- `pX`: prior distribution _P(X)_ over the support of _X_ `xs` as a Dictionary, e.g., `pX[x]` = _P(X=x)_
- `pZ_given_X`: likelihood _P(Z|X)_ as a Dictionary of Dictionaries, e.g., `pZ_given_X[x][z]` = _P(Z=z|X=x)_
- `z`: observed value of _Z_
"""
function bayesian_inference(xs, pX, pZ_given_X, z)
    # compute p(z)
    pz = sum(pZ_given_X[x][z]*pX[x] for x in xs)
    # compute p(X|z)
    pX_given_z = Dict(x => (pZ_given_X[x][z]*pX[x])/pz for x in xs)
    return pX_given_z
end
;
In [13]:
Random.seed!(0970252)

# set the true state of the tiger and the observations, these are unknown to the agent
true_state = :TigerRight
false_state = :TigerLeft
true_observations = :HearRight
false_observations = :HearLeft

println("Initial Probabilities: ", pX)
println()
# Start listening until we are sure where the tiger is
while all(pX[x] < 0.9 for x in xs)
    # listen and get observation
    z = rand(Binomial(1, pZ_given_X[true_state][true_observations])) == 1 ? true_observations : false_observations
    println("Observation: ", z)
    # bayesian inference
    pX = bayesian_inference(xs, pX, pZ_given_X, z)
    println("Probabilities: ", pX)
    println()
end

println("True Tiger location:\t", true_state)
println("Agent thinks that:\t", argmax(pX))
Initial Probabilities: Dict(:TigerLeft => 0.5, :TigerRight => 0.5)

Observation: HearLeft
Probabilities: Dict(:TigerLeft => 0.7272727272727273, :TigerRight => 0.2727272727272727)

Observation: HearRight
Probabilities: Dict(:TigerLeft => 0.4324324324324325, :TigerRight => 0.5675675675675675)

Observation: HearRight
Probabilities: Dict(:TigerLeft => 0.17877094972067045, :TigerRight => 0.8212290502793296)

Observation: HearRight
Probabilities: Dict(:TigerLeft => 0.05855443732845382, :TigerRight => 0.9414455626715462)

True Tiger location:	TigerRight
Agent thinks that:	TigerRight

Transition model and observation model - Bayesian update in 1D¶


Example:

Variable $x \in \mathbb{N}$ represents the position of a robot on a 1D line. The variable changes through time as the robots moves, i.e. $\{ x_0, x_1, x_2, ... \}$.
The robot does not know it's true position, but it maintains a distribution over it's possible position at each time step $t$.
$X_t$ is the random variable representing the position of the robot at time $t$.

The robot has a prior distribution about it's initial position, $\mathbb{P}(X_0)$.
Each time step $t$ the robot moves according to an action $a_t$, which changes it's position at the next time step. This is the transition model of $X_t$ over time, $\mathbb{P}(X_{t+1} \mid X_{t}, a_{t})$.
After the action is performed and position changed to $x_{t+1}$, the robot gets an observation from it's new position, $z_{t+1}$. This is the observation model for each time step $t$, $\mathbb{P}(Z_t \mid X_t)$.
The robot uses the observation to update the posterior distribution over it's position, $\mathbb{P}(X_t \mid a_{0:t-1}, z_{1:t})$.
The robot's estimation of it's position at each time $t$ is the Maximum a posteriori (MAP) estimator: $$ x^*_{t} = \argmax_{x_t} \mathbb{P}(x_t \mid a_{0:t-1}, z_{1:t})$$

In this example we consider:

  • Prior distribution: $\mathbb{P}(X_0) \sim \mathcal{U}\{-19,20\}$ (discrete uniform distribution).
  • Transition model: $X_{t+1} = X_{t} + a_{t} + \omega_{t}$, where $a_t \in \{-1,+1\}$ and $\omega_{t} = \begin{cases} 0, & \text{w.p.} ~ 0.8 \\ +1, & \text{w.p.} ~ 0.1 \\ -1, & \text{w.p.} ~ 0.1 \\ \end{cases}$, and independent of $X_t$.
  • Observation model: $Z_{t} = X_{t} + \nu_{t}$, where $\nu_{t} = \begin{cases} 0, & \text{w.p.} ~ 0.7 \\ +1, & \text{w.p.} ~ 0.15 \\ -1, & \text{w.p.} ~ 0.15 \\ \end{cases}$, and independent of $X_t$.
In [14]:
# Note: you can change these parameters to see how the estimation changes.
x0 = -2 # initial true position

xs = range(-19,20)
pX0 = Dict(x => 1/length(xs) for x in xs) # initial distribution - uniform

w = Dict(0 => 0.8, 1 => 0.1, -1 => 0.1) # motion disturbance
v = Dict(0 => 0.7, 1 => 0.15, -1 => 0.15) # observation noise

get_sample(d) = rand(POMDPTools.SparseCat(keys(d),values(d)))
;
In [15]:
Random.seed!(0970252)

n_steps = 100
controls = [-1, 1] # possible actions of the agent

xt = x0 # true position over time
xt_list = [xt]

pXt = pX0 # distribution over time
est_xt_list = [argmax(pXt)]

println("0: Robot at: ", xt_list[end])
println("0: Estimated position: ", est_xt_list[end])
println()

for t in 1:n_steps
    at = rand(controls) # random control
    # actual movement
    xt += at + get_sample(w)
    zt = xt + get_sample(v)
    push!(xt_list, xt)
    println(t, ": Performed action: ", at)
    println(t, ": Robot moved to: ", xt)
    println(t, ": Robot observed: ", zt)


    # prediction step (perform the action)
    pX_pred = Dict{Int, Float64}()
    for x in keys(pXt)
        for u in keys(w)
            x_pred = x + at + u
            # Note: if x_pred is not in the keys, get!() creates a new key for it with value 0, then we add the new probability
            #       if x_pred is already in the keys, get!() returns its current probability value, then we add the new probability
            pX_pred[x_pred] = get!(pX_pred, x_pred, 0) + pXt[x]*w[u]
        end
    end

    # compute p(zt)
    pzt = 0.0
    for x in keys(pX_pred)
        for u in keys(v)
            if zt == x + u
                pzt += pX_pred[x]*v[u]
            end
        end
    end

    # update step (inference)
    pXt = Dict{Int, Float64}()
    for x in keys(pX_pred)
        for u in keys(v)
            if zt == x + u
                # for a specific value x, there is at most one value u that satisfies zt == x + u
                pXt[x] = (pX_pred[x]*v[u])/pzt
            end
        end
    end
    
    # MAP estimator
    push!(est_xt_list, argmax(pXt))

    println(t, ": Estimated position: ", est_xt_list[end])
    println()
end

# Calculate RMSE of the MAP estimator
rmse = round(sqrt(mean((xt_list .- est_xt_list).^2)), digits=4)

plot(0:n_steps, xt_list, title="RMSE = $(rmse)", label="True position", xlabel="t", ylabel="position", marker=:circle, markersize=3)
plot!(0:n_steps, est_xt_list, label="MAP position", marker=:square, markersize=3)
0: Robot at: -2
0: Estimated position: -12

1: Performed action: -1
1: Robot moved to: -3
1: Robot observed: -3
1: Estimated position: -3

2: Performed action: 1
2: Robot moved to: -2
2: Robot observed: -2
2: Estimated position: -2

3: Performed action: 1
3: Robot moved to: -1
3: Robot observed: -1
3: Estimated position: -1

4: Performed action: -1
4: Robot moved to: -2
4: Robot observed: -2
4: Estimated position: -2

5: Performed action: 1
5: Robot moved to: -1
5: Robot observed: -1
5: Estimated position: -1

6: Performed action: 1
6: Robot moved to: 0
6: Robot observed: 0
6: Estimated position: 0

7: Performed action: -1
7: Robot moved to: -1
7: Robot observed: -2
7: Estimated position: -1

8: Performed action: 1
8: Robot moved to: -1
8: Robot observed: -2
8: Estimated position: -1

9: Performed action: 1
9: Robot moved to: 0
9: Robot observed: 1
9: Estimated position: 0

10: Performed action: 1
10: Robot moved to: 1
10: Robot observed: 1
10: Estimated position: 1

11: Performed action: 1
11: Robot moved to: 2
11: Robot observed: 1
11: Estimated position: 2

12: Performed action: -1
12: Robot moved to: 0
12: Robot observed: -1
12: Estimated position: 0

13: Performed action: 1
13: Robot moved to: 1
13: Robot observed: 0
13: Estimated position: 0

14: Performed action: -1
14: Robot moved to: 1
14: Robot observed: 0
14: Estimated position: 0

15: Performed action: 1
15: Robot moved to: 2
15: Robot observed: 3
15: Estimated position: 2

16: Performed action: 1
16: Robot moved to: 3
16: Robot observed: 4
16: Estimated position: 3

17: Performed action: -1
17: Robot moved to: 1
17: Robot observed: 1
17: Estimated position: 2

18: Performed action: -1
18: Robot moved to: 0
18: Robot observed: 1
18: Estimated position: 1

19: Performed action: 1
19: Robot moved to: 0
19: Robot observed: 0
19: Estimated position: 1

20: Performed action: 1
20: Robot moved to: 2
20: Robot observed: 2
20: Estimated position: 2

21: Performed action: -1
21: Robot moved to: 1
21: Robot observed: 1
21: Estimated position: 1

22: Performed action: -1
22: Robot moved to: 0
22: Robot observed: 0
22: Estimated position: 0

23: Performed action: 1
23: Robot moved to: 0
23: Robot observed: 0
23: Estimated position: 1

24: Performed action: -1
24: Robot moved to: -1
24: Robot observed: -1
24: Estimated position: -1

25: Performed action: -1
25: Robot moved to: -2
25: Robot observed: -2
25: Estimated position: -2

26: Performed action: 1
26: Robot moved to: -1
26: Robot observed: -1
26: Estimated position: -1

27: Performed action: 1
27: Robot moved to: -1
27: Robot observed: 0
27: Estimated position: 0

28: Performed action: 1
28: Robot moved to: 0
28: Robot observed: 0
28: Estimated position: 1

29: Performed action: 1
29: Robot moved to: 1
29: Robot observed: 1
29: Estimated position: 1

30: Performed action: 1
30: Robot moved to: 2
30: Robot observed: 2
30: Estimated position: 2

31: Performed action: 1
31: Robot moved to: 3
31: Robot observed: 4
31: Estimated position: 3

32: Performed action: -1
32: Robot moved to: 2
32: Robot observed: 2
32: Estimated position: 2

33: Performed action: 1
33: Robot moved to: 3
33: Robot observed: 3
33: Estimated position: 3

34: Performed action: -1
34: Robot moved to: 3
34: Robot observed: 3
34: Estimated position: 2

35: Performed action: -1
35: Robot moved to: 2
35: Robot observed: 2
35: Estimated position: 2

36: Performed action: 1
36: Robot moved to: 3
36: Robot observed: 4
36: Estimated position: 3

37: Performed action: 1
37: Robot moved to: 3
37: Robot observed: 3
37: Estimated position: 4

38: Performed action: -1
38: Robot moved to: 2
38: Robot observed: 2
38: Estimated position: 2

39: Performed action: -1
39: Robot moved to: 0
39: Robot observed: -1
39: Estimated position: 0

40: Performed action: -1
40: Robot moved to: -2
40: Robot observed: -3
40: Estimated position: -2

41: Performed action: -1
41: Robot moved to: -3
41: Robot observed: -4
41: Estimated position: -4

42: Performed action: -1
42: Robot moved to: -4
42: Robot observed: -4
42: Estimated position: -4

43: Performed action: -1
43: Robot moved to: -5
43: Robot observed: -4
43: Estimated position: -5

44: Performed action: -1
44: Robot moved to: -6
44: Robot observed: -6
44: Estimated position: -6

45: Performed action: -1
45: Robot moved to: -7
45: Robot observed: -7
45: Estimated position: -7

46: Performed action: -1
46: Robot moved to: -8
46: Robot observed: -8
46: Estimated position: -8

47: Performed action: 1
47: Robot moved to: -7
47: Robot observed: -7
47: Estimated position: -7

48: Performed action: -1
48: Robot moved to: -8
48: Robot observed: -8
48: Estimated position: -8

49: Performed action: 1
49: Robot moved to: -8
49: Robot observed: -7
49: Estimated position: -7

50: Performed action: 1
50: Robot moved to: -7
50: Robot observed: -7
50: Estimated position: -6

51: Performed action: 1
51: Robot moved to: -6
51: Robot observed: -6
51: Estimated position: -6

52: Performed action: -1
52: Robot moved to: -7
52: Robot observed: -6
52: Estimated position: -6

53: Performed action: 1
53: Robot moved to: -6
53: Robot observed: -6
53: Estimated position: -6

54: Performed action: -1
54: Robot moved to: -7
54: Robot observed: -7
54: Estimated position: -7

55: Performed action: -1
55: Robot moved to: -8
55: Robot observed: -8
55: Estimated position: -8

56: Performed action: 1
56: Robot moved to: -7
56: Robot observed: -7
56: Estimated position: -7

57: Performed action: 1
57: Robot moved to: -7
57: Robot observed: -7
57: Estimated position: -6

58: Performed action: -1
58: Robot moved to: -8
58: Robot observed: -8
58: Estimated position: -8

59: Performed action: -1
59: Robot moved to: -9
59: Robot observed: -8
59: Estimated position: -8

60: Performed action: 1
60: Robot moved to: -8
60: Robot observed: -8
60: Estimated position: -8

61: Performed action: 1
61: Robot moved to: -7
61: Robot observed: -7
61: Estimated position: -7

62: Performed action: 1
62: Robot moved to: -5
62: Robot observed: -4
62: Estimated position: -5

63: Performed action: 1
63: Robot moved to: -4
63: Robot observed: -4
63: Estimated position: -4

64: Performed action: -1
64: Robot moved to: -5
64: Robot observed: -5
64: Estimated position: -5

65: Performed action: 1
65: Robot moved to: -4
65: Robot observed: -4
65: Estimated position: -4

66: Performed action: -1
66: Robot moved to: -5
66: Robot observed: -5
66: Estimated position: -5

67: Performed action: 1
67: Robot moved to: -4
67: Robot observed: -5
67: Estimated position: -4

68: Performed action: -1
68: Robot moved to: -5
68: Robot observed: -5
68: Estimated position: -5

69: Performed action: 1
69: Robot moved to: -4
69: Robot observed: -3
69: Estimated position: -4

70: Performed action: 1
70: Robot moved to: -3
70: Robot observed: -3
70: Estimated position: -3

71: Performed action: -1
71: Robot moved to: -4
71: Robot observed: -4
71: Estimated position: -4

72: Performed action: 1
72: Robot moved to: -3
72: Robot observed: -3
72: Estimated position: -3

73: Performed action: 1
73: Robot moved to: -2
73: Robot observed: -2
73: Estimated position: -2

74: Performed action: 1
74: Robot moved to: -1
74: Robot observed: -1
74: Estimated position: -1

75: Performed action: 1
75: Robot moved to: 1
75: Robot observed: 2
75: Estimated position: 1

76: Performed action: 1
76: Robot moved to: 2
76: Robot observed: 2
76: Estimated position: 2

77: Performed action: 1
77: Robot moved to: 3
77: Robot observed: 3
77: Estimated position: 3

78: Performed action: -1
78: Robot moved to: 2
78: Robot observed: 2
78: Estimated position: 2

79: Performed action: -1
79: Robot moved to: 2
79: Robot observed: 2
79: Estimated position: 1

80: Performed action: 1
80: Robot moved to: 3
80: Robot observed: 2
80: Estimated position: 2

81: Performed action: 1
81: Robot moved to: 4
81: Robot observed: 4
81: Estimated position: 4

82: Performed action: 1
82: Robot moved to: 6
82: Robot observed: 6
82: Estimated position: 5

83: Performed action: -1
83: Robot moved to: 5
83: Robot observed: 5
83: Estimated position: 5

84: Performed action: -1
84: Robot moved to: 4
84: Robot observed: 4
84: Estimated position: 4

85: Performed action: -1
85: Robot moved to: 3
85: Robot observed: 3
85: Estimated position: 3

86: Performed action: 1
86: Robot moved to: 4
86: Robot observed: 4
86: Estimated position: 4

87: Performed action: 1
87: Robot moved to: 5
87: Robot observed: 5
87: Estimated position: 5

88: Performed action: 1
88: Robot moved to: 6
88: Robot observed: 7
88: Estimated position: 6

89: Performed action: 1
89: Robot moved to: 7
89: Robot observed: 7
89: Estimated position: 7

90: Performed action: 1
90: Robot moved to: 8
90: Robot observed: 8
90: Estimated position: 8

91: Performed action: 1
91: Robot moved to: 9
91: Robot observed: 9
91: Estimated position: 9

92: Performed action: -1
92: Robot moved to: 8
92: Robot observed: 9
92: Estimated position: 8

93: Performed action: -1
93: Robot moved to: 8
93: Robot observed: 8
93: Estimated position: 8

94: Performed action: 1
94: Robot moved to: 9
94: Robot observed: 9
94: Estimated position: 9

95: Performed action: 1
95: Robot moved to: 10
95: Robot observed: 10
95: Estimated position: 10

96: Performed action: 1
96: Robot moved to: 11
96: Robot observed: 12
96: Estimated position: 11

97: Performed action: -1
97: Robot moved to: 10
97: Robot observed: 10
97: Estimated position: 10

98: Performed action: 1
98: Robot moved to: 11
98: Robot observed: 11
98: Estimated position: 11

99: Performed action: -1
99: Robot moved to: 11
99: Robot observed: 10
99: Estimated position: 10

100: Performed action: 1
100: Robot moved to: 12
100: Robot observed: 13
100: Estimated position: 12

Out[15]:

Occupancy Grid Map (2D)¶


A 2D occupancy grid map $m = \{ m_{ij} \}$ is a matrix where each element $m_{ij}$ represents the cell $(i, j)$.
The probability that the cell $m_{ij}$ is occupied is defined as $p_{ij}$: $$ p_{ij} = \mathbb{P}(m_{ij} = 1) = \mathbb{P}(\text{cell } (i,j) \text{ is occupied}) $$ Assuming the cells are independent of each other, the probability of the occupancy map: $$ \mathbb{P}(m) = \prod_{i,j} \mathbb{P}(m_{ij}) = \prod_{i,j} p_{ij} $$

In [16]:
Random.seed!(0970252)

map = [
    1 1 0 0 0 0 0 0 1 1;
    1 0 0 0 1 0 0 0 0 1;
    0 0 0 1 0 0 0 0 0 0;
    0 0 1 0 0 0 1 1 0 0;
    0 0 1 0 0 0 0 0 0 0;
    0 0 1 0 0 0 0 0 0 0;
    0 0 1 0 0 0 1 1 0 0;
    0 0 0 1 0 0 0 0 0 0;
    1 0 0 0 1 0 0 0 0 1;
    1 1 0 0 0 0 0 0 1 1
]
nx, ny = size(map)

heatmap(map', c=cgrad(:grays, rev=true), title="True Map", xlabel='x', ylabel='y', legend=false, size=(400,400))
Out[16]:
In [17]:
# Observation model of the robot
pzOcc_given_mOcc = 0.9   # P(Z=occupied | cell=occupied)
pzOcc_given_mFree = 0.3   # P(Z=occupied | cell=free)

"""
Perform Bayesian Inference to update the probability of a cell being occupied, based on the given observation.
- `pmOcc`: probability of the cell being occupied
- `z`: observation of the cell (1 = occupied, 0 = free)
"""
function cell_bayesian_inference(pmOcc, z)
    if z == 1 # observation is occupied
        pz = pzOcc_given_mOcc * pmOcc + pzOcc_given_mFree * (1 - pmOcc)
        pmOcc_next = pzOcc_given_mOcc * pmOcc
        return pmOcc_next / pz
    else # observation is occupied
        pz = (1 - pzOcc_given_mOcc) * pmOcc + (1 - pzOcc_given_mFree) * (1 - pmOcc)
        pmOcc_next = (1 - pzOcc_given_mOcc) * pmOcc
        return pmOcc_next / pz
    end
end

"""
Select a random valid next position from the current position (x, y).
Valid moves are within bounds of the map.
If there are no valid moves, stay in the same position.
- `x`, `x`: current position
- `nx`, `ny`: size of the map
"""
function next_position(x, y, nx, ny)
    # possible moves: up, down, left, right
    moves = [(0,1), (0,-1), (1,0), (-1,0)]
    valid_positions = [(x+dx, y+dy) for (dx,dy) in moves if (0 < x+dx <= nx) && (0 < y+dy <= ny)]
    return isempty(valid_positions) ? (x, y) : rand(valid_positions)
end
;
In [18]:
Random.seed!(0970252)

# log_odds_map = zeros(nx,ny) # log-odds representation of the occupancy grid, initialized to 0 (p=0.5 for all cells)
prob_map = ones(nx,ny)*0.5 # initialized to p_occupied=0.5 for all cells

robot_pos = (1, 1) # starting position of the robot
n_steps = 1000

anim = @animate for iter in 1:n_steps
    # move to a new position
    global robot_pos = next_position(robot_pos[1], robot_pos[2], nx, ny)

    # simulate observation at the new position, assuming for simplicity the observation is noise free
    z = map[robot_pos...]
    println("Step ", iter, ": Robot moved to: ", robot_pos, ", observed: ", z == 1 ? "occupied" : "free")

    # update probability for the observed cell
    prob_map[robot_pos...] = cell_bayesian_inference(prob_map[robot_pos...], z)

    # visualize the current distribution of the map
    heatmap(prob_map', c=cgrad(:grays, rev=true), title="Map distribution @t=$iter", xlabel='x', ylabel='y', size=(400,400))
    scatter!([robot_pos[1]], [robot_pos[2]], markersize=10, markercolor=:red, label="Robot")
end
;
Step 1: Robot moved to: (1, 2), observed: occupied
Step 2: Robot moved to: (1, 3), observed: free
Step 3: Robot moved to: (1, 4), observed: free
Step 4: Robot moved to: (2, 4), observed: free
Step 5: Robot moved to: (3, 4), observed: occupied
Step 6: Robot moved to: (3, 5), observed: free
Step 7: Robot moved to: (2, 5), observed: occupied
Step 8: Robot moved to: (2, 6), observed: free
Step 9: Robot moved to: (2, 5), observed: occupied
Step 10: Robot moved to: (2, 4), observed: free
Step 11: Robot moved to: (2, 3), observed: free
Step 12: Robot moved to: (2, 4), observed: free
Step 13: Robot moved to: (1, 4), observed: free
Step 14: Robot moved to: (1, 5), observed: free
Step 15: Robot moved to: (1, 6), observed: free
Step 16: Robot moved to: (1, 5), observed: free
Step 17: Robot moved to: (1, 4), observed: free
Step 18: Robot moved to: (1, 5), observed: free
Step 19: Robot moved to: (1, 4), observed: free
Step 20: Robot moved to: (1, 5), observed: free
Step 21: Robot moved to: (2, 5), observed: occupied
Step 22: Robot moved to: (3, 5), observed: free
Step 23: Robot moved to: (2, 5), observed: occupied
Step 24: Robot moved to: (1, 5), observed: free
Step 25: Robot moved to: (2, 5), observed: occupied
Step 26: Robot moved to: (3, 5), observed: free
Step 27: Robot moved to: (2, 5), observed: occupied
Step 28: Robot moved to: (3, 5), observed: free
Step 29: Robot moved to: (3, 6), observed: free
Step 30: Robot moved to: (3, 5), observed: free
Step 31: Robot moved to: (2, 5), observed: occupied
Step 32: Robot moved to: (2, 4), observed: free
Step 33: Robot moved to: (3, 4), observed: occupied
Step 34: Robot moved to: (3, 5), observed: free
Step 35: Robot moved to: (2, 5), observed: occupied
Step 36: Robot moved to: (1, 5), observed: free
Step 37: Robot moved to: (2, 5), observed: occupied
Step 38: Robot moved to: (3, 5), observed: free
Step 39: Robot moved to: (2, 5), observed: occupied
Step 40: Robot moved to: (2, 6), observed: free
Step 41: Robot moved to: (1, 6), observed: free
Step 42: Robot moved to: (2, 6), observed: free
Step 43: Robot moved to: (3, 6), observed: free
Step 44: Robot moved to: (4, 6), observed: free
Step 45: Robot moved to: (3, 6), observed: free
Step 46: Robot moved to: (2, 6), observed: free
Step 47: Robot moved to: (2, 7), observed: free
Step 48: Robot moved to: (1, 7), observed: free
Step 49: Robot moved to: (1, 8), observed: free
Step 50: Robot moved to: (2, 8), observed: free
Step 51: Robot moved to: (3, 8), observed: free
Step 52: Robot moved to: (3, 9), observed: free
Step 53: Robot moved to: (4, 9), observed: free
Step 54: Robot moved to: (3, 9), observed: free
Step 55: Robot moved to: (4, 9), observed: free
Step 56: Robot moved to: (3, 9), observed: free
Step 57: Robot moved to: (3, 8), observed: free
Step 58: Robot moved to: (4, 8), observed: occupied
Step 59: Robot moved to: (3, 8), observed: free
Step 60: Robot moved to: (3, 7), observed: free
Step 61: Robot moved to: (3, 6), observed: free
Step 62: Robot moved to: (3, 5), observed: free
Step 63: Robot moved to: (4, 5), observed: free
Step 64: Robot moved to: (4, 6), observed: free
Step 65: Robot moved to: (4, 5), observed: free
Step 66: Robot moved to: (4, 4), observed: free
Step 67: Robot moved to: (5, 4), observed: free
Step 68: Robot moved to: (4, 4), observed: free
Step 69: Robot moved to: (4, 3), observed: occupied
Step 70: Robot moved to: (4, 2), observed: free
Step 71: Robot moved to: (5, 2), observed: free
Step 72: Robot moved to: (6, 2), observed: free
Step 73: Robot moved to: (6, 1), observed: free
Step 74: Robot moved to: (6, 2), observed: free
Step 75: Robot moved to: (6, 3), observed: occupied
Step 76: Robot moved to: (7, 3), observed: occupied
Step 77: Robot moved to: (7, 2), observed: free
Step 78: Robot moved to: (7, 1), observed: free
Step 79: Robot moved to: (6, 1), observed: free
Step 80: Robot moved to: (5, 1), observed: free
Step 81: Robot moved to: (4, 1), observed: free
Step 82: Robot moved to: (5, 1), observed: free
Step 83: Robot moved to: (6, 1), observed: free
Step 84: Robot moved to: (7, 1), observed: free
Step 85: Robot moved to: (6, 1), observed: free
Step 86: Robot moved to: (7, 1), observed: free
Step 87: Robot moved to: (8, 1), observed: free
Step 88: Robot moved to: (7, 1), observed: free
Step 89: Robot moved to: (8, 1), observed: free
Step 90: Robot moved to: (8, 2), observed: free
Step 91: Robot moved to: (7, 2), observed: free
Step 92: Robot moved to: (7, 1), observed: free
Step 93: Robot moved to: (6, 1), observed: free
Step 94: Robot moved to: (6, 2), observed: free
Step 95: Robot moved to: (6, 1), observed: free
Step 96: Robot moved to: (6, 2), observed: free
Step 97: Robot moved to: (7, 2), observed: free
Step 98: Robot moved to: (8, 2), observed: free
Step 99: Robot moved to: (8, 3), observed: free
Step 100: Robot moved to: (8, 2), observed: free
Step 101: Robot moved to: (7, 2), observed: free
Step 102: Robot moved to: (7, 3), observed: occupied
Step 103: Robot moved to: (7, 2), observed: free
Step 104: Robot moved to: (6, 2), observed: free
Step 105: Robot moved to: (6, 3), observed: occupied
Step 106: Robot moved to: (7, 3), observed: occupied
Step 107: Robot moved to: (7, 4), observed: free
Step 108: Robot moved to: (6, 4), observed: free
Step 109: Robot moved to: (7, 4), observed: free
Step 110: Robot moved to: (6, 4), observed: free
Step 111: Robot moved to: (6, 3), observed: occupied
Step 112: Robot moved to: (6, 4), observed: free
Step 113: Robot moved to: (6, 3), observed: occupied
Step 114: Robot moved to: (6, 2), observed: free
Step 115: Robot moved to: (6, 1), observed: free
Step 116: Robot moved to: (5, 1), observed: free
Step 117: Robot moved to: (4, 1), observed: free
Step 118: Robot moved to: (5, 1), observed: free
Step 119: Robot moved to: (4, 1), observed: free
Step 120: Robot moved to: (3, 1), observed: free
Step 121: Robot moved to: (3, 2), observed: free
Step 122: Robot moved to: (3, 1), observed: free
Step 123: Robot moved to: (2, 1), observed: occupied
Step 124: Robot moved to: (2, 2), observed: free
Step 125: Robot moved to: (2, 3), observed: free
Step 126: Robot moved to: (2, 4), observed: free
Step 127: Robot moved to: (2, 3), observed: free
Step 128: Robot moved to: (2, 4), observed: free
Step 129: Robot moved to: (1, 4), observed: free
Step 130: Robot moved to: (1, 5), observed: free
Step 131: Robot moved to: (1, 6), observed: free
Step 132: Robot moved to: (1, 7), observed: free
Step 133: Robot moved to: (1, 6), observed: free
Step 134: Robot moved to: (1, 7), observed: free
Step 135: Robot moved to: (1, 6), observed: free
Step 136: Robot moved to: (1, 5), observed: free
Step 137: Robot moved to: (2, 5), observed: occupied
Step 138: Robot moved to: (2, 4), observed: free
Step 139: Robot moved to: (1, 4), observed: free
Step 140: Robot moved to: (1, 5), observed: free
Step 141: Robot moved to: (1, 4), observed: free
Step 142: Robot moved to: (1, 5), observed: free
Step 143: Robot moved to: (2, 5), observed: occupied
Step 144: Robot moved to: (3, 5), observed: free
Step 145: Robot moved to: (4, 5), observed: free
Step 146: Robot moved to: (3, 5), observed: free
Step 147: Robot moved to: (2, 5), observed: occupied
Step 148: Robot moved to: (3, 5), observed: free
Step 149: Robot moved to: (3, 6), observed: free
Step 150: Robot moved to: (4, 6), observed: free
Step 151: Robot moved to: (5, 6), observed: free
Step 152: Robot moved to: (5, 7), observed: free
Step 153: Robot moved to: (5, 8), observed: free
Step 154: Robot moved to: (5, 7), observed: free
Step 155: Robot moved to: (5, 8), observed: free
Step 156: Robot moved to: (4, 8), observed: occupied
Step 157: Robot moved to: (3, 8), observed: free
Step 158: Robot moved to: (3, 9), observed: free
Step 159: Robot moved to: (4, 9), observed: free
Step 160: Robot moved to: (4, 8), observed: occupied
Step 161: Robot moved to: (5, 8), observed: free
Step 162: Robot moved to: (5, 7), observed: free
Step 163: Robot moved to: (5, 8), observed: free
Step 164: Robot moved to: (6, 8), observed: free
Step 165: Robot moved to: (6, 7), observed: free
Step 166: Robot moved to: (7, 7), observed: occupied
Step 167: Robot moved to: (7, 8), observed: occupied
Step 168: Robot moved to: (7, 9), observed: free
Step 169: Robot moved to: (6, 9), observed: free
Step 170: Robot moved to: (5, 9), observed: free
Step 171: Robot moved to: (6, 9), observed: free
Step 172: Robot moved to: (6, 10), observed: free
Step 173: Robot moved to: (7, 10), observed: free
Step 174: Robot moved to: (8, 10), observed: free
Step 175: Robot moved to: (8, 9), observed: free
Step 176: Robot moved to: (8, 10), observed: free
Step 177: Robot moved to: (7, 10), observed: free
Step 178: Robot moved to: (6, 10), observed: free
Step 179: Robot moved to: (6, 9), observed: free
Step 180: Robot moved to: (6, 8), observed: free
Step 181: Robot moved to: (5, 8), observed: free
Step 182: Robot moved to: (4, 8), observed: occupied
Step 183: Robot moved to: (4, 9), observed: free
Step 184: Robot moved to: (5, 9), observed: free
Step 185: Robot moved to: (4, 9), observed: free
Step 186: Robot moved to: (3, 9), observed: free
Step 187: Robot moved to: (2, 9), observed: free
Step 188: Robot moved to: (2, 10), observed: occupied
Step 189: Robot moved to: (2, 9), observed: free
Step 190: Robot moved to: (2, 10), observed: occupied
Step 191: Robot moved to: (2, 9), observed: free
Step 192: Robot moved to: (2, 10), observed: occupied
Step 193: Robot moved to: (1, 10), observed: occupied
Step 194: Robot moved to: (1, 9), observed: occupied
Step 195: Robot moved to: (1, 8), observed: free
Step 196: Robot moved to: (1, 9), observed: occupied
Step 197: Robot moved to: (1, 8), observed: free
Step 198: Robot moved to: (1, 7), observed: free
Step 199: Robot moved to: (2, 7), observed: free
Step 200: Robot moved to: (3, 7), observed: free
Step 201: Robot moved to: (4, 7), observed: occupied
Step 202: Robot moved to: (4, 8), observed: occupied
Step 203: Robot moved to: (5, 8), observed: free
Step 204: Robot moved to: (5, 9), observed: free
Step 205: Robot moved to: (4, 9), observed: free
Step 206: Robot moved to: (4, 10), observed: free
Step 207: Robot moved to: (3, 10), observed: free
Step 208: Robot moved to: (4, 10), observed: free
Step 209: Robot moved to: (5, 10), observed: free
Step 210: Robot moved to: (6, 10), observed: free
Step 211: Robot moved to: (7, 10), observed: free
Step 212: Robot moved to: (7, 9), observed: free
Step 213: Robot moved to: (8, 9), observed: free
Step 214: Robot moved to: (7, 9), observed: free
Step 215: Robot moved to: (8, 9), observed: free
Step 216: Robot moved to: (8, 8), observed: free
Step 217: Robot moved to: (9, 8), observed: free
Step 218: Robot moved to: (9, 7), observed: free
Step 219: Robot moved to: (9, 6), observed: free
Step 220: Robot moved to: (8, 6), observed: free
Step 221: Robot moved to: (8, 7), observed: free
Step 222: Robot moved to: (9, 7), observed: free
Step 223: Robot moved to: (10, 7), observed: free
Step 224: Robot moved to: (9, 7), observed: free
Step 225: Robot moved to: (8, 7), observed: free
Step 226: Robot moved to: (9, 7), observed: free
Step 227: Robot moved to: (9, 6), observed: free
Step 228: Robot moved to: (10, 6), observed: free
Step 229: Robot moved to: (9, 6), observed: free
Step 230: Robot moved to: (9, 7), observed: free
Step 231: Robot moved to: (9, 6), observed: free
Step 232: Robot moved to: (9, 7), observed: free
Step 233: Robot moved to: (10, 7), observed: free
Step 234: Robot moved to: (10, 8), observed: free
Step 235: Robot moved to: (10, 9), observed: occupied
Step 236: Robot moved to: (9, 9), observed: free
Step 237: Robot moved to: (9, 10), observed: occupied
Step 238: Robot moved to: (8, 10), observed: free
Step 239: Robot moved to: (8, 9), observed: free
Step 240: Robot moved to: (7, 9), observed: free
Step 241: Robot moved to: (6, 9), observed: free
Step 242: Robot moved to: (6, 10), observed: free
Step 243: Robot moved to: (7, 10), observed: free
Step 244: Robot moved to: (8, 10), observed: free
Step 245: Robot moved to: (7, 10), observed: free
Step 246: Robot moved to: (7, 9), observed: free
Step 247: Robot moved to: (7, 8), observed: occupied
Step 248: Robot moved to: (8, 8), observed: free
Step 249: Robot moved to: (8, 9), observed: free
Step 250: Robot moved to: (8, 8), observed: free
Step 251: Robot moved to: (9, 8), observed: free
Step 252: Robot moved to: (9, 9), observed: free
Step 253: Robot moved to: (9, 8), observed: free
Step 254: Robot moved to: (9, 9), observed: free
Step 255: Robot moved to: (9, 8), observed: free
Step 256: Robot moved to: (8, 8), observed: free
Step 257: Robot moved to: (9, 8), observed: free
Step 258: Robot moved to: (9, 9), observed: free
Step 259: Robot moved to: (10, 9), observed: occupied
Step 260: Robot moved to: (10, 10), observed: occupied
Step 261: Robot moved to: (10, 9), observed: occupied
Step 262: Robot moved to: (9, 9), observed: free
Step 263: Robot moved to: (9, 8), observed: free
Step 264: Robot moved to: (8, 8), observed: free
Step 265: Robot moved to: (9, 8), observed: free
Step 266: Robot moved to: (10, 8), observed: free
Step 267: Robot moved to: (10, 9), observed: occupied
Step 268: Robot moved to: (10, 8), observed: free
Step 269: Robot moved to: (10, 7), observed: free
Step 270: Robot moved to: (10, 8), observed: free
Step 271: Robot moved to: (9, 8), observed: free
Step 272: Robot moved to: (10, 8), observed: free
Step 273: Robot moved to: (10, 7), observed: free
Step 274: Robot moved to: (10, 8), observed: free
Step 275: Robot moved to: (10, 7), observed: free
Step 276: Robot moved to: (9, 7), observed: free
Step 277: Robot moved to: (9, 6), observed: free
Step 278: Robot moved to: (8, 6), observed: free
Step 279: Robot moved to: (9, 6), observed: free
Step 280: Robot moved to: (8, 6), observed: free
Step 281: Robot moved to: (8, 7), observed: free
Step 282: Robot moved to: (8, 8), observed: free
Step 283: Robot moved to: (7, 8), observed: occupied
Step 284: Robot moved to: (8, 8), observed: free
Step 285: Robot moved to: (9, 8), observed: free
Step 286: Robot moved to: (10, 8), observed: free
Step 287: Robot moved to: (10, 7), observed: free
Step 288: Robot moved to: (9, 7), observed: free
Step 289: Robot moved to: (9, 8), observed: free
Step 290: Robot moved to: (9, 9), observed: free
Step 291: Robot moved to: (9, 10), observed: occupied
Step 292: Robot moved to: (10, 10), observed: occupied
Step 293: Robot moved to: (9, 10), observed: occupied
Step 294: Robot moved to: (9, 9), observed: free
Step 295: Robot moved to: (9, 10), observed: occupied
Step 296: Robot moved to: (8, 10), observed: free
Step 297: Robot moved to: (7, 10), observed: free
Step 298: Robot moved to: (6, 10), observed: free
Step 299: Robot moved to: (6, 9), observed: free
Step 300: Robot moved to: (5, 9), observed: free
Step 301: Robot moved to: (4, 9), observed: free
Step 302: Robot moved to: (3, 9), observed: free
Step 303: Robot moved to: (3, 8), observed: free
Step 304: Robot moved to: (2, 8), observed: free
Step 305: Robot moved to: (2, 9), observed: free
Step 306: Robot moved to: (3, 9), observed: free
Step 307: Robot moved to: (2, 9), observed: free
Step 308: Robot moved to: (2, 8), observed: free
Step 309: Robot moved to: (2, 7), observed: free
Step 310: Robot moved to: (3, 7), observed: free
Step 311: Robot moved to: (4, 7), observed: occupied
Step 312: Robot moved to: (3, 7), observed: free
Step 313: Robot moved to: (3, 8), observed: free
Step 314: Robot moved to: (3, 9), observed: free
Step 315: Robot moved to: (4, 9), observed: free
Step 316: Robot moved to: (4, 10), observed: free
Step 317: Robot moved to: (3, 10), observed: free
Step 318: Robot moved to: (4, 10), observed: free
Step 319: Robot moved to: (4, 9), observed: free
Step 320: Robot moved to: (5, 9), observed: free
Step 321: Robot moved to: (6, 9), observed: free
Step 322: Robot moved to: (6, 10), observed: free
Step 323: Robot moved to: (7, 10), observed: free
Step 324: Robot moved to: (8, 10), observed: free
Step 325: Robot moved to: (8, 9), observed: free
Step 326: Robot moved to: (8, 10), observed: free
Step 327: Robot moved to: (8, 9), observed: free
Step 328: Robot moved to: (8, 10), observed: free
Step 329: Robot moved to: (7, 10), observed: free
Step 330: Robot moved to: (7, 9), observed: free
Step 331: Robot moved to: (7, 8), observed: occupied
Step 332: Robot moved to: (8, 8), observed: free
Step 333: Robot moved to: (8, 7), observed: free
Step 334: Robot moved to: (8, 8), observed: free
Step 335: Robot moved to: (8, 9), observed: free
Step 336: Robot moved to: (8, 10), observed: free
Step 337: Robot moved to: (7, 10), observed: free
Step 338: Robot moved to: (6, 10), observed: free
Step 339: Robot moved to: (7, 10), observed: free
Step 340: Robot moved to: (8, 10), observed: free
Step 341: Robot moved to: (7, 10), observed: free
Step 342: Robot moved to: (7, 9), observed: free
Step 343: Robot moved to: (6, 9), observed: free
Step 344: Robot moved to: (5, 9), observed: free
Step 345: Robot moved to: (6, 9), observed: free
Step 346: Robot moved to: (6, 10), observed: free
Step 347: Robot moved to: (5, 10), observed: free
Step 348: Robot moved to: (6, 10), observed: free
Step 349: Robot moved to: (7, 10), observed: free
Step 350: Robot moved to: (6, 10), observed: free
Step 351: Robot moved to: (7, 10), observed: free
Step 352: Robot moved to: (7, 9), observed: free
Step 353: Robot moved to: (6, 9), observed: free
Step 354: Robot moved to: (7, 9), observed: free
Step 355: Robot moved to: (6, 9), observed: free
Step 356: Robot moved to: (6, 8), observed: free
Step 357: Robot moved to: (5, 8), observed: free
Step 358: Robot moved to: (5, 7), observed: free
Step 359: Robot moved to: (5, 8), observed: free
Step 360: Robot moved to: (6, 8), observed: free
Step 361: Robot moved to: (6, 9), observed: free
Step 362: Robot moved to: (6, 8), observed: free
Step 363: Robot moved to: (5, 8), observed: free
Step 364: Robot moved to: (5, 7), observed: free
Step 365: Robot moved to: (6, 7), observed: free
Step 366: Robot moved to: (7, 7), observed: occupied
Step 367: Robot moved to: (8, 7), observed: free
Step 368: Robot moved to: (8, 8), observed: free
Step 369: Robot moved to: (8, 7), observed: free
Step 370: Robot moved to: (8, 6), observed: free
Step 371: Robot moved to: (7, 6), observed: free
Step 372: Robot moved to: (6, 6), observed: free
Step 373: Robot moved to: (6, 7), observed: free
Step 374: Robot moved to: (7, 7), observed: occupied
Step 375: Robot moved to: (7, 6), observed: free
Step 376: Robot moved to: (7, 7), observed: occupied
Step 377: Robot moved to: (8, 7), observed: free
Step 378: Robot moved to: (9, 7), observed: free
Step 379: Robot moved to: (9, 8), observed: free
Step 380: Robot moved to: (8, 8), observed: free
Step 381: Robot moved to: (9, 8), observed: free
Step 382: Robot moved to: (9, 7), observed: free
Step 383: Robot moved to: (9, 8), observed: free
Step 384: Robot moved to: (9, 9), observed: free
Step 385: Robot moved to: (10, 9), observed: occupied
Step 386: Robot moved to: (10, 10), observed: occupied
Step 387: Robot moved to: (9, 10), observed: occupied
Step 388: Robot moved to: (10, 10), observed: occupied
Step 389: Robot moved to: (10, 9), observed: occupied
Step 390: Robot moved to: (10, 10), observed: occupied
Step 391: Robot moved to: (9, 10), observed: occupied
Step 392: Robot moved to: (10, 10), observed: occupied
Step 393: Robot moved to: (9, 10), observed: occupied
Step 394: Robot moved to: (9, 9), observed: free
Step 395: Robot moved to: (9, 10), observed: occupied
Step 396: Robot moved to: (9, 9), observed: free
Step 397: Robot moved to: (9, 10), observed: occupied
Step 398: Robot moved to: (9, 9), observed: free
Step 399: Robot moved to: (9, 10), observed: occupied
Step 400: Robot moved to: (8, 10), observed: free
Step 401: Robot moved to: (9, 10), observed: occupied
Step 402: Robot moved to: (8, 10), observed: free
Step 403: Robot moved to: (8, 9), observed: free
Step 404: Robot moved to: (7, 9), observed: free
Step 405: Robot moved to: (6, 9), observed: free
Step 406: Robot moved to: (6, 8), observed: free
Step 407: Robot moved to: (5, 8), observed: free
Step 408: Robot moved to: (6, 8), observed: free
Step 409: Robot moved to: (6, 9), observed: free
Step 410: Robot moved to: (7, 9), observed: free
Step 411: Robot moved to: (7, 8), observed: occupied
Step 412: Robot moved to: (6, 8), observed: free
Step 413: Robot moved to: (7, 8), observed: occupied
Step 414: Robot moved to: (7, 9), observed: free
Step 415: Robot moved to: (7, 8), observed: occupied
Step 416: Robot moved to: (7, 7), observed: occupied
Step 417: Robot moved to: (7, 6), observed: free
Step 418: Robot moved to: (7, 7), observed: occupied
Step 419: Robot moved to: (8, 7), observed: free
Step 420: Robot moved to: (7, 7), observed: occupied
Step 421: Robot moved to: (8, 7), observed: free
Step 422: Robot moved to: (9, 7), observed: free
Step 423: Robot moved to: (9, 8), observed: free
Step 424: Robot moved to: (8, 8), observed: free
Step 425: Robot moved to: (7, 8), observed: occupied
Step 426: Robot moved to: (6, 8), observed: free
Step 427: Robot moved to: (5, 8), observed: free
Step 428: Robot moved to: (5, 9), observed: free
Step 429: Robot moved to: (4, 9), observed: free
Step 430: Robot moved to: (5, 9), observed: free
Step 431: Robot moved to: (4, 9), observed: free
Step 432: Robot moved to: (4, 8), observed: occupied
Step 433: Robot moved to: (4, 9), observed: free
Step 434: Robot moved to: (3, 9), observed: free
Step 435: Robot moved to: (3, 10), observed: free
Step 436: Robot moved to: (3, 9), observed: free
Step 437: Robot moved to: (2, 9), observed: free
Step 438: Robot moved to: (3, 9), observed: free
Step 439: Robot moved to: (3, 10), observed: free
Step 440: Robot moved to: (3, 9), observed: free
Step 441: Robot moved to: (4, 9), observed: free
Step 442: Robot moved to: (4, 10), observed: free
Step 443: Robot moved to: (3, 10), observed: free
Step 444: Robot moved to: (3, 9), observed: free
Step 445: Robot moved to: (2, 9), observed: free
Step 446: Robot moved to: (2, 8), observed: free
Step 447: Robot moved to: (2, 9), observed: free
Step 448: Robot moved to: (2, 8), observed: free
Step 449: Robot moved to: (1, 8), observed: free
Step 450: Robot moved to: (2, 8), observed: free
Step 451: Robot moved to: (2, 9), observed: free
Step 452: Robot moved to: (1, 9), observed: occupied
Step 453: Robot moved to: (1, 10), observed: occupied
Step 454: Robot moved to: (2, 10), observed: occupied
Step 455: Robot moved to: (3, 10), observed: free
Step 456: Robot moved to: (3, 9), observed: free
Step 457: Robot moved to: (2, 9), observed: free
Step 458: Robot moved to: (1, 9), observed: occupied
Step 459: Robot moved to: (1, 8), observed: free
Step 460: Robot moved to: (1, 7), observed: free
Step 461: Robot moved to: (1, 6), observed: free
Step 462: Robot moved to: (1, 5), observed: free
Step 463: Robot moved to: (1, 4), observed: free
Step 464: Robot moved to: (2, 4), observed: free
Step 465: Robot moved to: (2, 3), observed: free
Step 466: Robot moved to: (2, 4), observed: free
Step 467: Robot moved to: (1, 4), observed: free
Step 468: Robot moved to: (1, 5), observed: free
Step 469: Robot moved to: (1, 4), observed: free
Step 470: Robot moved to: (1, 5), observed: free
Step 471: Robot moved to: (2, 5), observed: occupied
Step 472: Robot moved to: (2, 6), observed: free
Step 473: Robot moved to: (2, 7), observed: free
Step 474: Robot moved to: (3, 7), observed: free
Step 475: Robot moved to: (2, 7), observed: free
Step 476: Robot moved to: (2, 8), observed: free
Step 477: Robot moved to: (2, 7), observed: free
Step 478: Robot moved to: (1, 7), observed: free
Step 479: Robot moved to: (1, 8), observed: free
Step 480: Robot moved to: (1, 7), observed: free
Step 481: Robot moved to: (2, 7), observed: free
Step 482: Robot moved to: (1, 7), observed: free
Step 483: Robot moved to: (1, 8), observed: free
Step 484: Robot moved to: (2, 8), observed: free
Step 485: Robot moved to: (1, 8), observed: free
Step 486: Robot moved to: (1, 7), observed: free
Step 487: Robot moved to: (2, 7), observed: free
Step 488: Robot moved to: (1, 7), observed: free
Step 489: Robot moved to: (2, 7), observed: free
Step 490: Robot moved to: (2, 6), observed: free
Step 491: Robot moved to: (2, 5), observed: occupied
Step 492: Robot moved to: (2, 6), observed: free
Step 493: Robot moved to: (1, 6), observed: free
Step 494: Robot moved to: (1, 5), observed: free
Step 495: Robot moved to: (1, 4), observed: free
Step 496: Robot moved to: (1, 3), observed: free
Step 497: Robot moved to: (2, 3), observed: free
Step 498: Robot moved to: (3, 3), observed: free
Step 499: Robot moved to: (2, 3), observed: free
Step 500: Robot moved to: (2, 2), observed: free
Step 501: Robot moved to: (1, 2), observed: occupied
Step 502: Robot moved to: (1, 3), observed: free
Step 503: Robot moved to: (2, 3), observed: free
Step 504: Robot moved to: (2, 4), observed: free
Step 505: Robot moved to: (2, 3), observed: free
Step 506: Robot moved to: (3, 3), observed: free
Step 507: Robot moved to: (2, 3), observed: free
Step 508: Robot moved to: (2, 4), observed: free
Step 509: Robot moved to: (1, 4), observed: free
Step 510: Robot moved to: (1, 5), observed: free
Step 511: Robot moved to: (1, 6), observed: free
Step 512: Robot moved to: (2, 6), observed: free
Step 513: Robot moved to: (2, 7), observed: free
Step 514: Robot moved to: (2, 6), observed: free
Step 515: Robot moved to: (2, 5), observed: occupied
Step 516: Robot moved to: (1, 5), observed: free
Step 517: Robot moved to: (2, 5), observed: occupied
Step 518: Robot moved to: (3, 5), observed: free
Step 519: Robot moved to: (3, 6), observed: free
Step 520: Robot moved to: (2, 6), observed: free
Step 521: Robot moved to: (2, 7), observed: free
Step 522: Robot moved to: (1, 7), observed: free
Step 523: Robot moved to: (1, 6), observed: free
Step 524: Robot moved to: (1, 5), observed: free
Step 525: Robot moved to: (2, 5), observed: occupied
Step 526: Robot moved to: (1, 5), observed: free
Step 527: Robot moved to: (2, 5), observed: occupied
Step 528: Robot moved to: (2, 4), observed: free
Step 529: Robot moved to: (2, 3), observed: free
Step 530: Robot moved to: (1, 3), observed: free
Step 531: Robot moved to: (2, 3), observed: free
Step 532: Robot moved to: (2, 2), observed: free
Step 533: Robot moved to: (1, 2), observed: occupied
Step 534: Robot moved to: (1, 1), observed: occupied
Step 535: Robot moved to: (2, 1), observed: occupied
Step 536: Robot moved to: (1, 1), observed: occupied
Step 537: Robot moved to: (1, 2), observed: occupied
Step 538: Robot moved to: (1, 3), observed: free
Step 539: Robot moved to: (2, 3), observed: free
Step 540: Robot moved to: (2, 2), observed: free
Step 541: Robot moved to: (1, 2), observed: occupied
Step 542: Robot moved to: (1, 3), observed: free
Step 543: Robot moved to: (1, 4), observed: free
Step 544: Robot moved to: (1, 5), observed: free
Step 545: Robot moved to: (1, 6), observed: free
Step 546: Robot moved to: (1, 7), observed: free
Step 547: Robot moved to: (2, 7), observed: free
Step 548: Robot moved to: (2, 6), observed: free
Step 549: Robot moved to: (3, 6), observed: free
Step 550: Robot moved to: (2, 6), observed: free
Step 551: Robot moved to: (2, 5), observed: occupied
Step 552: Robot moved to: (2, 6), observed: free
Step 553: Robot moved to: (1, 6), observed: free
Step 554: Robot moved to: (1, 5), observed: free
Step 555: Robot moved to: (1, 6), observed: free
Step 556: Robot moved to: (1, 7), observed: free
Step 557: Robot moved to: (1, 8), observed: free
Step 558: Robot moved to: (1, 7), observed: free
Step 559: Robot moved to: (1, 8), observed: free
Step 560: Robot moved to: (1, 9), observed: occupied
Step 561: Robot moved to: (1, 10), observed: occupied
Step 562: Robot moved to: (1, 9), observed: occupied
Step 563: Robot moved to: (1, 8), observed: free
Step 564: Robot moved to: (1, 9), observed: occupied
Step 565: Robot moved to: (2, 9), observed: free
Step 566: Robot moved to: (3, 9), observed: free
Step 567: Robot moved to: (3, 10), observed: free
Step 568: Robot moved to: (3, 9), observed: free
Step 569: Robot moved to: (3, 8), observed: free
Step 570: Robot moved to: (3, 7), observed: free
Step 571: Robot moved to: (4, 7), observed: occupied
Step 572: Robot moved to: (4, 8), observed: occupied
Step 573: Robot moved to: (4, 7), observed: occupied
Step 574: Robot moved to: (4, 8), observed: occupied
Step 575: Robot moved to: (3, 8), observed: free
Step 576: Robot moved to: (3, 9), observed: free
Step 577: Robot moved to: (2, 9), observed: free
Step 578: Robot moved to: (2, 8), observed: free
Step 579: Robot moved to: (1, 8), observed: free
Step 580: Robot moved to: (1, 9), observed: occupied
Step 581: Robot moved to: (1, 8), observed: free
Step 582: Robot moved to: (1, 9), observed: occupied
Step 583: Robot moved to: (1, 10), observed: occupied
Step 584: Robot moved to: (1, 9), observed: occupied
Step 585: Robot moved to: (1, 10), observed: occupied
Step 586: Robot moved to: (2, 10), observed: occupied
Step 587: Robot moved to: (3, 10), observed: free
Step 588: Robot moved to: (3, 9), observed: free
Step 589: Robot moved to: (3, 10), observed: free
Step 590: Robot moved to: (2, 10), observed: occupied
Step 591: Robot moved to: (1, 10), observed: occupied
Step 592: Robot moved to: (2, 10), observed: occupied
Step 593: Robot moved to: (1, 10), observed: occupied
Step 594: Robot moved to: (2, 10), observed: occupied
Step 595: Robot moved to: (2, 9), observed: free
Step 596: Robot moved to: (1, 9), observed: occupied
Step 597: Robot moved to: (2, 9), observed: free
Step 598: Robot moved to: (2, 10), observed: occupied
Step 599: Robot moved to: (1, 10), observed: occupied
Step 600: Robot moved to: (2, 10), observed: occupied
Step 601: Robot moved to: (3, 10), observed: free
Step 602: Robot moved to: (2, 10), observed: occupied
Step 603: Robot moved to: (3, 10), observed: free
Step 604: Robot moved to: (4, 10), observed: free
Step 605: Robot moved to: (5, 10), observed: free
Step 606: Robot moved to: (6, 10), observed: free
Step 607: Robot moved to: (5, 10), observed: free
Step 608: Robot moved to: (4, 10), observed: free
Step 609: Robot moved to: (5, 10), observed: free
Step 610: Robot moved to: (6, 10), observed: free
Step 611: Robot moved to: (6, 9), observed: free
Step 612: Robot moved to: (5, 9), observed: free
Step 613: Robot moved to: (6, 9), observed: free
Step 614: Robot moved to: (7, 9), observed: free
Step 615: Robot moved to: (6, 9), observed: free
Step 616: Robot moved to: (5, 9), observed: free
Step 617: Robot moved to: (5, 8), observed: free
Step 618: Robot moved to: (4, 8), observed: occupied
Step 619: Robot moved to: (3, 8), observed: free
Step 620: Robot moved to: (4, 8), observed: occupied
Step 621: Robot moved to: (4, 7), observed: occupied
Step 622: Robot moved to: (4, 6), observed: free
Step 623: Robot moved to: (5, 6), observed: free
Step 624: Robot moved to: (4, 6), observed: free
Step 625: Robot moved to: (4, 5), observed: free
Step 626: Robot moved to: (3, 5), observed: free
Step 627: Robot moved to: (4, 5), observed: free
Step 628: Robot moved to: (4, 6), observed: free
Step 629: Robot moved to: (4, 7), observed: occupied
Step 630: Robot moved to: (4, 8), observed: occupied
Step 631: Robot moved to: (4, 9), observed: free
Step 632: Robot moved to: (5, 9), observed: free
Step 633: Robot moved to: (5, 8), observed: free
Step 634: Robot moved to: (5, 9), observed: free
Step 635: Robot moved to: (5, 10), observed: free
Step 636: Robot moved to: (4, 10), observed: free
Step 637: Robot moved to: (4, 9), observed: free
Step 638: Robot moved to: (3, 9), observed: free
Step 639: Robot moved to: (3, 10), observed: free
Step 640: Robot moved to: (4, 10), observed: free
Step 641: Robot moved to: (5, 10), observed: free
Step 642: Robot moved to: (6, 10), observed: free
Step 643: Robot moved to: (6, 9), observed: free
Step 644: Robot moved to: (5, 9), observed: free
Step 645: Robot moved to: (4, 9), observed: free
Step 646: Robot moved to: (4, 10), observed: free
Step 647: Robot moved to: (3, 10), observed: free
Step 648: Robot moved to: (4, 10), observed: free
Step 649: Robot moved to: (3, 10), observed: free
Step 650: Robot moved to: (2, 10), observed: occupied
Step 651: Robot moved to: (1, 10), observed: occupied
Step 652: Robot moved to: (2, 10), observed: occupied
Step 653: Robot moved to: (3, 10), observed: free
Step 654: Robot moved to: (4, 10), observed: free
Step 655: Robot moved to: (3, 10), observed: free
Step 656: Robot moved to: (2, 10), observed: occupied
Step 657: Robot moved to: (3, 10), observed: free
Step 658: Robot moved to: (2, 10), observed: occupied
Step 659: Robot moved to: (1, 10), observed: occupied
Step 660: Robot moved to: (1, 9), observed: occupied
Step 661: Robot moved to: (1, 8), observed: free
Step 662: Robot moved to: (1, 7), observed: free
Step 663: Robot moved to: (2, 7), observed: free
Step 664: Robot moved to: (2, 8), observed: free
Step 665: Robot moved to: (1, 8), observed: free
Step 666: Robot moved to: (1, 7), observed: free
Step 667: Robot moved to: (2, 7), observed: free
Step 668: Robot moved to: (1, 7), observed: free
Step 669: Robot moved to: (1, 6), observed: free
Step 670: Robot moved to: (1, 7), observed: free
Step 671: Robot moved to: (1, 6), observed: free
Step 672: Robot moved to: (1, 5), observed: free
Step 673: Robot moved to: (1, 6), observed: free
Step 674: Robot moved to: (2, 6), observed: free
Step 675: Robot moved to: (3, 6), observed: free
Step 676: Robot moved to: (3, 7), observed: free
Step 677: Robot moved to: (3, 8), observed: free
Step 678: Robot moved to: (3, 9), observed: free
Step 679: Robot moved to: (3, 10), observed: free
Step 680: Robot moved to: (4, 10), observed: free
Step 681: Robot moved to: (5, 10), observed: free
Step 682: Robot moved to: (5, 9), observed: free
Step 683: Robot moved to: (5, 8), observed: free
Step 684: Robot moved to: (6, 8), observed: free
Step 685: Robot moved to: (6, 9), observed: free
Step 686: Robot moved to: (6, 8), observed: free
Step 687: Robot moved to: (5, 8), observed: free
Step 688: Robot moved to: (5, 7), observed: free
Step 689: Robot moved to: (4, 7), observed: occupied
Step 690: Robot moved to: (3, 7), observed: free
Step 691: Robot moved to: (3, 8), observed: free
Step 692: Robot moved to: (3, 9), observed: free
Step 693: Robot moved to: (2, 9), observed: free
Step 694: Robot moved to: (2, 8), observed: free
Step 695: Robot moved to: (1, 8), observed: free
Step 696: Robot moved to: (1, 7), observed: free
Step 697: Robot moved to: (2, 7), observed: free
Step 698: Robot moved to: (1, 7), observed: free
Step 699: Robot moved to: (2, 7), observed: free
Step 700: Robot moved to: (2, 6), observed: free
Step 701: Robot moved to: (1, 6), observed: free
Step 702: Robot moved to: (2, 6), observed: free
Step 703: Robot moved to: (2, 7), observed: free
Step 704: Robot moved to: (2, 6), observed: free
Step 705: Robot moved to: (1, 6), observed: free
Step 706: Robot moved to: (1, 5), observed: free
Step 707: Robot moved to: (1, 6), observed: free
Step 708: Robot moved to: (1, 7), observed: free
Step 709: Robot moved to: (1, 8), observed: free
Step 710: Robot moved to: (1, 9), observed: occupied
Step 711: Robot moved to: (1, 8), observed: free
Step 712: Robot moved to: (2, 8), observed: free
Step 713: Robot moved to: (2, 9), observed: free
Step 714: Robot moved to: (3, 9), observed: free
Step 715: Robot moved to: (2, 9), observed: free
Step 716: Robot moved to: (1, 9), observed: occupied
Step 717: Robot moved to: (1, 8), observed: free
Step 718: Robot moved to: (2, 8), observed: free
Step 719: Robot moved to: (3, 8), observed: free
Step 720: Robot moved to: (3, 7), observed: free
Step 721: Robot moved to: (3, 6), observed: free
Step 722: Robot moved to: (3, 7), observed: free
Step 723: Robot moved to: (3, 8), observed: free
Step 724: Robot moved to: (3, 9), observed: free
Step 725: Robot moved to: (4, 9), observed: free
Step 726: Robot moved to: (3, 9), observed: free
Step 727: Robot moved to: (2, 9), observed: free
Step 728: Robot moved to: (2, 10), observed: occupied
Step 729: Robot moved to: (1, 10), observed: occupied
Step 730: Robot moved to: (2, 10), observed: occupied
Step 731: Robot moved to: (1, 10), observed: occupied
Step 732: Robot moved to: (1, 9), observed: occupied
Step 733: Robot moved to: (1, 10), observed: occupied
Step 734: Robot moved to: (1, 9), observed: occupied
Step 735: Robot moved to: (1, 10), observed: occupied
Step 736: Robot moved to: (2, 10), observed: occupied
Step 737: Robot moved to: (1, 10), observed: occupied
Step 738: Robot moved to: (2, 10), observed: occupied
Step 739: Robot moved to: (2, 9), observed: free
Step 740: Robot moved to: (1, 9), observed: occupied
Step 741: Robot moved to: (2, 9), observed: free
Step 742: Robot moved to: (1, 9), observed: occupied
Step 743: Robot moved to: (2, 9), observed: free
Step 744: Robot moved to: (2, 8), observed: free
Step 745: Robot moved to: (3, 8), observed: free
Step 746: Robot moved to: (3, 7), observed: free
Step 747: Robot moved to: (3, 8), observed: free
Step 748: Robot moved to: (3, 7), observed: free
Step 749: Robot moved to: (3, 8), observed: free
Step 750: Robot moved to: (2, 8), observed: free
Step 751: Robot moved to: (3, 8), observed: free
Step 752: Robot moved to: (3, 7), observed: free
Step 753: Robot moved to: (3, 8), observed: free
Step 754: Robot moved to: (4, 8), observed: occupied
Step 755: Robot moved to: (4, 9), observed: free
Step 756: Robot moved to: (4, 8), observed: occupied
Step 757: Robot moved to: (5, 8), observed: free
Step 758: Robot moved to: (4, 8), observed: occupied
Step 759: Robot moved to: (3, 8), observed: free
Step 760: Robot moved to: (3, 9), observed: free
Step 761: Robot moved to: (4, 9), observed: free
Step 762: Robot moved to: (5, 9), observed: free
Step 763: Robot moved to: (6, 9), observed: free
Step 764: Robot moved to: (7, 9), observed: free
Step 765: Robot moved to: (7, 10), observed: free
Step 766: Robot moved to: (6, 10), observed: free
Step 767: Robot moved to: (7, 10), observed: free
Step 768: Robot moved to: (6, 10), observed: free
Step 769: Robot moved to: (7, 10), observed: free
Step 770: Robot moved to: (8, 10), observed: free
Step 771: Robot moved to: (9, 10), observed: occupied
Step 772: Robot moved to: (8, 10), observed: free
Step 773: Robot moved to: (7, 10), observed: free
Step 774: Robot moved to: (8, 10), observed: free
Step 775: Robot moved to: (7, 10), observed: free
Step 776: Robot moved to: (6, 10), observed: free
Step 777: Robot moved to: (7, 10), observed: free
Step 778: Robot moved to: (6, 10), observed: free
Step 779: Robot moved to: (6, 9), observed: free
Step 780: Robot moved to: (5, 9), observed: free
Step 781: Robot moved to: (4, 9), observed: free
Step 782: Robot moved to: (3, 9), observed: free
Step 783: Robot moved to: (4, 9), observed: free
Step 784: Robot moved to: (4, 8), observed: occupied
Step 785: Robot moved to: (3, 8), observed: free
Step 786: Robot moved to: (2, 8), observed: free
Step 787: Robot moved to: (1, 8), observed: free
Step 788: Robot moved to: (1, 9), observed: occupied
Step 789: Robot moved to: (2, 9), observed: free
Step 790: Robot moved to: (1, 9), observed: occupied
Step 791: Robot moved to: (2, 9), observed: free
Step 792: Robot moved to: (3, 9), observed: free
Step 793: Robot moved to: (3, 10), observed: free
Step 794: Robot moved to: (3, 9), observed: free
Step 795: Robot moved to: (3, 10), observed: free
Step 796: Robot moved to: (3, 9), observed: free
Step 797: Robot moved to: (3, 10), observed: free
Step 798: Robot moved to: (2, 10), observed: occupied
Step 799: Robot moved to: (2, 9), observed: free
Step 800: Robot moved to: (3, 9), observed: free
Step 801: Robot moved to: (2, 9), observed: free
Step 802: Robot moved to: (2, 8), observed: free
Step 803: Robot moved to: (2, 7), observed: free
Step 804: Robot moved to: (1, 7), observed: free
Step 805: Robot moved to: (1, 8), observed: free
Step 806: Robot moved to: (1, 9), observed: occupied
Step 807: Robot moved to: (1, 8), observed: free
Step 808: Robot moved to: (1, 9), observed: occupied
Step 809: Robot moved to: (1, 8), observed: free
Step 810: Robot moved to: (1, 9), observed: occupied
Step 811: Robot moved to: (1, 10), observed: occupied
Step 812: Robot moved to: (1, 9), observed: occupied
Step 813: Robot moved to: (1, 10), observed: occupied
Step 814: Robot moved to: (2, 10), observed: occupied
Step 815: Robot moved to: (2, 9), observed: free
Step 816: Robot moved to: (3, 9), observed: free
Step 817: Robot moved to: (3, 10), observed: free
Step 818: Robot moved to: (2, 10), observed: occupied
Step 819: Robot moved to: (3, 10), observed: free
Step 820: Robot moved to: (2, 10), observed: occupied
Step 821: Robot moved to: (3, 10), observed: free
Step 822: Robot moved to: (4, 10), observed: free
Step 823: Robot moved to: (3, 10), observed: free
Step 824: Robot moved to: (3, 9), observed: free
Step 825: Robot moved to: (4, 9), observed: free
Step 826: Robot moved to: (5, 9), observed: free
Step 827: Robot moved to: (4, 9), observed: free
Step 828: Robot moved to: (5, 9), observed: free
Step 829: Robot moved to: (5, 10), observed: free
Step 830: Robot moved to: (6, 10), observed: free
Step 831: Robot moved to: (5, 10), observed: free
Step 832: Robot moved to: (6, 10), observed: free
Step 833: Robot moved to: (7, 10), observed: free
Step 834: Robot moved to: (6, 10), observed: free
Step 835: Robot moved to: (7, 10), observed: free
Step 836: Robot moved to: (8, 10), observed: free
Step 837: Robot moved to: (7, 10), observed: free
Step 838: Robot moved to: (8, 10), observed: free
Step 839: Robot moved to: (7, 10), observed: free
Step 840: Robot moved to: (6, 10), observed: free
Step 841: Robot moved to: (5, 10), observed: free
Step 842: Robot moved to: (5, 9), observed: free
Step 843: Robot moved to: (4, 9), observed: free
Step 844: Robot moved to: (3, 9), observed: free
Step 845: Robot moved to: (4, 9), observed: free
Step 846: Robot moved to: (3, 9), observed: free
Step 847: Robot moved to: (3, 8), observed: free
Step 848: Robot moved to: (3, 9), observed: free
Step 849: Robot moved to: (2, 9), observed: free
Step 850: Robot moved to: (3, 9), observed: free
Step 851: Robot moved to: (2, 9), observed: free
Step 852: Robot moved to: (2, 10), observed: occupied
Step 853: Robot moved to: (1, 10), observed: occupied
Step 854: Robot moved to: (2, 10), observed: occupied
Step 855: Robot moved to: (1, 10), observed: occupied
Step 856: Robot moved to: (1, 9), observed: occupied
Step 857: Robot moved to: (2, 9), observed: free
Step 858: Robot moved to: (2, 10), observed: occupied
Step 859: Robot moved to: (3, 10), observed: free
Step 860: Robot moved to: (4, 10), observed: free
Step 861: Robot moved to: (4, 9), observed: free
Step 862: Robot moved to: (4, 8), observed: occupied
Step 863: Robot moved to: (4, 7), observed: occupied
Step 864: Robot moved to: (5, 7), observed: free
Step 865: Robot moved to: (5, 8), observed: free
Step 866: Robot moved to: (4, 8), observed: occupied
Step 867: Robot moved to: (4, 9), observed: free
Step 868: Robot moved to: (4, 8), observed: occupied
Step 869: Robot moved to: (5, 8), observed: free
Step 870: Robot moved to: (4, 8), observed: occupied
Step 871: Robot moved to: (3, 8), observed: free
Step 872: Robot moved to: (2, 8), observed: free
Step 873: Robot moved to: (2, 9), observed: free
Step 874: Robot moved to: (3, 9), observed: free
Step 875: Robot moved to: (3, 10), observed: free
Step 876: Robot moved to: (3, 9), observed: free
Step 877: Robot moved to: (2, 9), observed: free
Step 878: Robot moved to: (3, 9), observed: free
Step 879: Robot moved to: (4, 9), observed: free
Step 880: Robot moved to: (5, 9), observed: free
Step 881: Robot moved to: (5, 8), observed: free
Step 882: Robot moved to: (4, 8), observed: occupied
Step 883: Robot moved to: (4, 7), observed: occupied
Step 884: Robot moved to: (3, 7), observed: free
Step 885: Robot moved to: (3, 8), observed: free
Step 886: Robot moved to: (4, 8), observed: occupied
Step 887: Robot moved to: (4, 7), observed: occupied
Step 888: Robot moved to: (3, 7), observed: free
Step 889: Robot moved to: (3, 6), observed: free
Step 890: Robot moved to: (3, 5), observed: free
Step 891: Robot moved to: (3, 6), observed: free
Step 892: Robot moved to: (3, 7), observed: free
Step 893: Robot moved to: (3, 8), observed: free
Step 894: Robot moved to: (2, 8), observed: free
Step 895: Robot moved to: (2, 7), observed: free
Step 896: Robot moved to: (3, 7), observed: free
Step 897: Robot moved to: (3, 8), observed: free
Step 898: Robot moved to: (3, 9), observed: free
Step 899: Robot moved to: (2, 9), observed: free
Step 900: Robot moved to: (2, 10), observed: occupied
Step 901: Robot moved to: (2, 9), observed: free
Step 902: Robot moved to: (2, 10), observed: occupied
Step 903: Robot moved to: (3, 10), observed: free
Step 904: Robot moved to: (4, 10), observed: free
Step 905: Robot moved to: (3, 10), observed: free
Step 906: Robot moved to: (4, 10), observed: free
Step 907: Robot moved to: (4, 9), observed: free
Step 908: Robot moved to: (3, 9), observed: free
Step 909: Robot moved to: (3, 10), observed: free
Step 910: Robot moved to: (2, 10), observed: occupied
Step 911: Robot moved to: (3, 10), observed: free
Step 912: Robot moved to: (2, 10), observed: occupied
Step 913: Robot moved to: (2, 9), observed: free
Step 914: Robot moved to: (2, 10), observed: occupied
Step 915: Robot moved to: (2, 9), observed: free
Step 916: Robot moved to: (2, 10), observed: occupied
Step 917: Robot moved to: (2, 9), observed: free
Step 918: Robot moved to: (2, 10), observed: occupied
Step 919: Robot moved to: (2, 9), observed: free
Step 920: Robot moved to: (3, 9), observed: free
Step 921: Robot moved to: (2, 9), observed: free
Step 922: Robot moved to: (2, 8), observed: free
Step 923: Robot moved to: (2, 9), observed: free
Step 924: Robot moved to: (2, 10), observed: occupied
Step 925: Robot moved to: (1, 10), observed: occupied
Step 926: Robot moved to: (2, 10), observed: occupied
Step 927: Robot moved to: (1, 10), observed: occupied
Step 928: Robot moved to: (2, 10), observed: occupied
Step 929: Robot moved to: (2, 9), observed: free
Step 930: Robot moved to: (1, 9), observed: occupied
Step 931: Robot moved to: (1, 10), observed: occupied
Step 932: Robot moved to: (1, 9), observed: occupied
Step 933: Robot moved to: (1, 10), observed: occupied
Step 934: Robot moved to: (2, 10), observed: occupied
Step 935: Robot moved to: (2, 9), observed: free
Step 936: Robot moved to: (2, 10), observed: occupied
Step 937: Robot moved to: (1, 10), observed: occupied
Step 938: Robot moved to: (1, 9), observed: occupied
Step 939: Robot moved to: (1, 8), observed: free
Step 940: Robot moved to: (1, 9), observed: occupied
Step 941: Robot moved to: (1, 8), observed: free
Step 942: Robot moved to: (2, 8), observed: free
Step 943: Robot moved to: (3, 8), observed: free
Step 944: Robot moved to: (3, 9), observed: free
Step 945: Robot moved to: (2, 9), observed: free
Step 946: Robot moved to: (3, 9), observed: free
Step 947: Robot moved to: (3, 10), observed: free
Step 948: Robot moved to: (3, 9), observed: free
Step 949: Robot moved to: (3, 8), observed: free
Step 950: Robot moved to: (3, 9), observed: free
Step 951: Robot moved to: (2, 9), observed: free
Step 952: Robot moved to: (3, 9), observed: free
Step 953: Robot moved to: (2, 9), observed: free
Step 954: Robot moved to: (2, 8), observed: free
Step 955: Robot moved to: (2, 7), observed: free
Step 956: Robot moved to: (2, 6), observed: free
Step 957: Robot moved to: (2, 7), observed: free
Step 958: Robot moved to: (2, 6), observed: free
Step 959: Robot moved to: (1, 6), observed: free
Step 960: Robot moved to: (1, 7), observed: free
Step 961: Robot moved to: (1, 6), observed: free
Step 962: Robot moved to: (1, 7), observed: free
Step 963: Robot moved to: (1, 8), observed: free
Step 964: Robot moved to: (1, 9), observed: occupied
Step 965: Robot moved to: (2, 9), observed: free
Step 966: Robot moved to: (1, 9), observed: occupied
Step 967: Robot moved to: (1, 10), observed: occupied
Step 968: Robot moved to: (1, 9), observed: occupied
Step 969: Robot moved to: (1, 10), observed: occupied
Step 970: Robot moved to: (1, 9), observed: occupied
Step 971: Robot moved to: (1, 10), observed: occupied
Step 972: Robot moved to: (2, 10), observed: occupied
Step 973: Robot moved to: (3, 10), observed: free
Step 974: Robot moved to: (4, 10), observed: free
Step 975: Robot moved to: (3, 10), observed: free
Step 976: Robot moved to: (3, 9), observed: free
Step 977: Robot moved to: (3, 10), observed: free
Step 978: Robot moved to: (4, 10), observed: free
Step 979: Robot moved to: (3, 10), observed: free
Step 980: Robot moved to: (2, 10), observed: occupied
Step 981: Robot moved to: (2, 9), observed: free
Step 982: Robot moved to: (2, 8), observed: free
Step 983: Robot moved to: (2, 9), observed: free
Step 984: Robot moved to: (3, 9), observed: free
Step 985: Robot moved to: (3, 8), observed: free
Step 986: Robot moved to: (3, 7), observed: free
Step 987: Robot moved to: (3, 6), observed: free
Step 988: Robot moved to: (4, 6), observed: free
Step 989: Robot moved to: (4, 7), observed: occupied
Step 990: Robot moved to: (4, 8), observed: occupied
Step 991: Robot moved to: (4, 9), observed: free
Step 992: Robot moved to: (5, 9), observed: free
Step 993: Robot moved to: (6, 9), observed: free
Step 994: Robot moved to: (6, 8), observed: free
Step 995: Robot moved to: (6, 7), observed: free
Step 996: Robot moved to: (5, 7), observed: free
Step 997: Robot moved to: (5, 6), observed: free
Step 998: Robot moved to: (5, 7), observed: free
Step 999: Robot moved to: (5, 6), observed: free
Step 1000: Robot moved to: (6, 6), observed: free
In [19]:
gif(anim, "./assets/occupancy_grid_mapping.gif")
[ Info: Saved animation to D:\ANPL\0970252-pomdp\Tutorials\assets\occupancy_grid_mapping.gif
Out[19]:
No description has been provided for this image

julia Using Julia¶


In this course we will use Julia for our code examples and implementations, and we encourage you to implement your homework in Julia as well.

To run this tutorial locally via VSCode you need to make sure you have Julia installed on your computer.

  • Installing Julia: Follow this guide or this guide to install Julia on your computer.

  • VSCode: To run the tutorial in VSCode:

    1. Follow this guide to install and use Julia in VSCode.
    2. Then, follow this guide to run jupyter notebooks directly in VSCode.
    3. After successfully finishing these steps, you can open the tutorial notebook, change the kernel to your installed Julia version, and run the tutorial code.

To run this tutorial in Google Colab you can upload it to colab (upload the contents of assets directory as well), set the runtime type to Julia and use a CPU, then run the tutorial.

We encourage you to work in VSCode directly, get familiar with Julia and implement your homework in .jl files, which allows a better debugging environment.
For more information about Julia please refer to the following sources:

  • https://julialang.org/
  • https://juliapackages.com/
  • https://docs.julialang.org/en/v1/

external-copyright-graphic-design-bearicons-outline-color-bearicons Credits¶


  • Icons from Icons8
  • TigerPOMDP image from People@EECS at UC Berkley